package 数据结构考纲.树;

import 力扣.公用数据结构.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Tree {
    //先序非递归
    public static void preorder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                //先序，在这里访问
                System.out.print(p.val + " ");
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                p = p.right;
            }
        }
        System.out.println();
    }

    //中序非递归
    public static void midorder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                //中序，在这里访问
                System.out.print(p.val + " ");
                p = p.right;
            }
        }
        System.out.println();
    }

    //后序非递归
    public static void afterorder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root, pre = null;  //pre用于记录前一个输出的节点
        //后序的非递归实现比较难，仅当右子树为空（左子树这时已被访问过），或右子树刚被访问时，才可输出栈顶
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.peek();   //读栈顶
                //左子树存在且未被访问过
                if (p.right != null && p.right != pre) {
                    p = p.right;    //向右继续
                } else {
                    p = stack.pop();
                    System.out.print(p.val + " ");
                    pre = p;
                    p = null;
                }
            }
        }
        System.out.println();
    }

    //层序遍历
    public static void LevelTravel(TreeNode root) {
        if (root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode t = queue.poll();
            System.out.print(t.val + " ");
            if (t.left != null)
                queue.add(t.left);
            if (t.right != null)
                queue.add(t.right);
        }
        System.out.println();
    }

    public static void fun(TreeNode root) {
        if (root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();//当前层节点数量
            while (size-- > 0) {    //将当前层的节点遍历
                TreeNode t = queue.poll();
                System.out.print(t.val + " ");
                if (t.left != null)
                    queue.add(t.left);
                if (t.right != null)
                    queue.add(t.right);
            }
            System.out.println();
        }
        System.out.println();
    }
    //二叉树转森林
    //哈夫曼树
    //建立AVL
    //建立BST


    public static void main(String[] args) {
        TreeNode tree = TreeNode.creat("[1,2,3,4,5,6,7]");
        //先序遍历
        preorder(tree);
        midorder(tree);
        afterorder(tree);
        LevelTravel(tree);
        fun(tree);
    }
}
